package DataStructure.array;

/**
 * 前缀和 案例
 */
public class PreSum {


    public static void main(String[] args) {
        System.out.println(maxAbsoluteSum(new int[]{1,2,-3,4,5}));
    }


    /**
     * 给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。
     * 请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。
     * @param nums
     * @return
     */
    public static int maxAbsoluteSum(int[] nums) {
        // 连续子数组的最值
        /**
         解析：
         子数组的和等于两个前缀和的差
         举例: 1,2,3,4,5
         子数组 4,5 的和 = 4+5 = 9 = (1+...+5) - (1+..+3)
         so
         最大子数组的和 就是最大前缀和 - 最小前缀和
         遍历数组 累加 得到最小前缀和和最大值前缀和
         */
        // 前缀和
        int preMin = 0;
        int preMax = 0;
        int sum = 0;
        for(int num : nums){
            // 前缀和
            sum += num;
            preMin = Math.min(preMin, sum);
            preMax = Math.max(preMax, sum);
        }
        return preMax - preMin;
    }



}
